package src.CodeTop;

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 *
 * 示例 1：
 *
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 *
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 *
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 *
 * 输入：s = "{[]}"
 * 输出：true
 */

public class _20ValidParentheses {
    public static void main(String[] args) {
        String s = "()";
        boolean target = isValid(s);
        System.out.println(target);
    }

    public static boolean isValid(String s) {
        // 校验合法性
        if (s == null)
            return false;
        // 将字符串分割为字符数组
        char[] chars = s.toCharArray();
        // 定义栈用来存放左括号
        Stack<Character> stack = new Stack<>();
        // 遍历字符数组
        for (int i = 0 ; i < chars.length ; i++) {
            // 获得当前的字符
            char cur = chars[i];
            // 若当前括号为左括号
            if (cur == '(' || cur == '[' || cur == '{') {
                // 将当前符号压栈
                stack.push(chars[i]);
            }else {
                // 若当前栈为空
                if (stack.isEmpty()) {
                    return false;
                }
                // 若当前括号为右括号以及栈顶为与之匹配的左括号
                if (cur == ')' && stack.peek() == '(') {
                    // 弹出栈顶括号
                    stack.pop();
                }else if (cur == ']' && stack.peek() == '[') {
                    // 弹出栈顶括号
                    stack.pop();
                }else if (cur == '}' && stack.peek() == '{') {
                    // 弹出栈顶括号
                    stack.pop();
                }else {
                    // 非有效括号
                    return false;
                }
            }
        }
        // 栈空则为真，不为空则为假
        return stack.isEmpty();
    }
}
